#include <bits/stdc++.h>
using namespace std;
int g;
const int maxans = 20;
int a[maxans];
bool dfs(int d, int maxd){
    if(d==maxd) return a[d]==g;
    int m = *max_element(a, a+d+1);
    if(m << (maxd-d) < g) return false;
    for (int i = d; i >= 0; --i) {
        a[d+1] = a[d] + a[i];
        if(dfs(d+1, maxd)) return true;
        a[d+1] = a[d] - a[i];
        if(dfs(d+1, maxd)) return true;
    }
    return false;
}

int solve(int n){
    if(n==1) return 0;
    for(int maxd = 1; ; ++maxd){
        a[0] = 1;
        if(dfs(0, maxd)) return maxd;
    }
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    while(cin >> g && g){
        cout << solve(g) << "\n";
    }
    return 0;
}